//
//  main.cpp
//  QuestionC++
//
//  Created by sr Liu on 2020/3/28.
//  Copyright © 2020 sr Liu. All rights reserved.
//

#include <iostream>
#include "DataStructHeader.h"
#include <stack>

#pragma mark - 面试题5：从尾到头打印链表
void printLinkListReverse(LinkList phead) {
    std::stack<LinkList> nodes;
    LinkList pnode = phead;
    while (pnode != NULL) {
        nodes.push(pnode);
        pnode = pnode->next;
    }
    while (!nodes.empty()) {
        pnode = nodes.top();
        printf("%d\t",pnode->data);
        nodes.pop();
    }
}

//因为递归本质上是一个栈结构,用递归实现下，但是递归调用栈太多不建议
void printLinkListReverseRecursive(LinkList phead) {
    if (phead != NULL) {
        if (phead->next != NULL) {
            printLinkListReverseRecursive(phead->next);
        }
        printf("%d\t",phead->data);
    }
}

//letcode：206 翻转链表，这个改变链表结构。

LinkList linkListReverse(LinkList phead) {
    LinkList curNode = phead;//记录一个当前的
    LinkList preNode = NULL;//记录上一个节点
    while (curNode != NULL) {//检查每个节点，也包含了参数phead为空
        LinkList tmpNode = curNode->next;
        curNode->next = preNode;
        preNode = curNode;
        curNode = tmpNode;
    }
    return preNode;
}

#pragma mark - 面试题23：从上往下打印二叉树
/**
从上往下打印二叉树的每个结点，同一层级的结点按照从左到右的顺序打印。（也叫层序遍历二叉树，广度优先遍历）
思路：将根结点放到队列中。每一次打印一个结点的时候(pop时)，如果该结点有子节点，就把该结点的子节点放入一个队列的末尾，接下来到队列头部取出最早入队的结点。重复进行直到队列为空。
*/
void PrintTreeFromTopToBottom(BinaryTree root) {
    if (root == NULL) {
        return;
    }
    std::deque<BinaryTreeNode *> dequeTreeNode;
    dequeTreeNode.push_back(root);
    
    while (dequeTreeNode.size()) {
        BinaryTreeNode *node = dequeTreeNode.front();
        dequeTreeNode.pop_front();
        printf("%d ",node->data);
        if (node->leftChild) {
            dequeTreeNode.push_back(node->leftChild);
        }
        if (node->rightChild) {
            dequeTreeNode.push_back(node->rightChild);
        }
    }
}


//TODO:-还有递归的没想明白


int main(int argc, const char * argv[]) {
    // insert code here...
    std::cout << "Hello, World!\n";
    return 0;
}
